// 2025/4/2
// https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-100-liked
// 编辑距离

class Solution {
    public:
        int minDistance(string word1, string word2) {
            int m = word1.size(), n = word2.size();
            vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
            for(int i = 1; i < m + 1; i++) dp[i][0] = i;
            for(int j = 1; j < n + 1; j++) dp[0][j] = j;
            for(int i = 1; i <= m; i++)
            {
                for(int j = 1; j <= n; j++)
                {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
                    int left_down = dp[i - 1][j - 1];
                    if(word1[i - 1] != word2[j - 1]) left_down++;
                    dp[i][j] = min(dp[i][j], left_down);
                }
            }
            return dp[m][n];
        }
    };